1. Field of the Invention
The present invention generally relates to data storage, and specifically to storage of video on a hard disk drive.
2. Background Art
Many users of satellite, cable, or even terrestrial video services have recently migrated from using analog magnetic media to record programming to digital video recorders (“DVRs”). DVRs take an input video from a video source, in digital format or in analog format by first digitizing the input video, and store the digital video on a fixed medium, such as a hard disk drive (“disk”). A user may subsequently select the recorded video for playback, record additional video, or delete the recorded video in order to free space in the disk for future recordings.
In a typical setup, a DVR is constantly connected to an input video source. Accordingly, many DVRs will automatically record the last 1-to-2 hours of actively watched live video in order to allow a user to quickly review anything the user has recently seen. Due to the temporary nature of this type of recording, the DVR will typically erase the automatically recorded video at some predefined interval.
As High Definition Television (“HDTV”) standards have become more common in consumer use, DVRs have evolved to record HDTV video. HDTV video includes high resolution images that require higher data storage needs for recording. A typical 2-to-3 hour HDTV recording can occupy a 15-to-20 Gigabyte (“GB”) file.
The DVR's disk, used to store recorded content, typically includes a contiguous memory area divided into blocks. Blocks on a disk are the smallest units in which data are read from and written to the disk. In a typical disk, block sizes are small, usually around 4 kilobytes (“kB”). With a 4 kB block size, a file comprising 7 kB worth of data will consume 8 kB of disk space, because it will fully consume a 4 kB block and will consume 3 kB of a second 4 kB block. However, the remaining 1 kB on the second block cannot be used to store additional data.
In traditional filesystems, a file's structure is typically kept in an inode. The inode includes pointers to each of the blocks of data necessary to construct the file.
These pointers may include a number of direct pointers, which point directly to blocks of the file's data, and some number of n-way (singly, doubly, etc.) indirect pointers. Indirect pointers are pointers that point to blocks of data that contain additional pointers. For each level of indirect access, there exists such a set of blocks of data containing additional pointers. At the final level of indirect access (the first level for indirect pointers, the second level for doubly indirect pointers, etc.), the pointers contained within the block of data are direct pointers.
Indirect pointers within an inode exist in order to allow individual files to encompass many blocks of data, and therefore allowing for very large file sizes. An inode with only direct access pointers would require the allocation, in advance, of memory for storing direct pointers to each block of data of the largest expected file size. Such an operation is wasteful when allocating smaller files. However, traversing several levels of indirection to access all of the blocks of data comprising a larger file is also expensive.
The typical 2-to-3 hour HDTV recording, occupying 15-to-20 GB of disk space, requires millions of 4 kB blocks to store the recording. Such a small block size is typically used in order to conserve space on the disk, as a 20 GB recording may consequently only waste most of a 4 kB block, an insignificant amount relative to the size of the recording. The drawback of using a small block size is, as noted, the sheer quantity of blocks needed to compose the recording. Small block sizes used to store files many times larger than the block size can often lead to a situation called fragmenting which may severely hinder the performance of a DVR attempting to read or write a video recording.
A disk will usually attempt to allocate to a recording a contiguous set of blocks that comprises a large enough disk area to store the entire file. After many such areas are allocated, and files are subsequently deleted, data remains-in locations throughout the disk, with areas of free, contiguous memory between them. If a new recording is made that is too large to fit within any of the free, contiguous memory locations, it is necessary to allocate block fragments, comprising groups of blocks from non-contiguous memory locations. A typical disk operates most efficiently when it is accessing contiguous blocks of memory, and having to read from or write to memory locations in various parts of the disk will slow down its access times. Furthermore, wear and tear on the disk is increased by having to access multiple fragmented blocks. As previously noted, traversing through several levels of indirect pointers to access a data block is costly, and becomes a more serious problem when the data blocks accessed as a result of a traversal through indirect pointers are not stored in a contiguous area of memory.
Due to the nature of standard filesystems, specifically memory to disk architecture requirements, it is often not possible to guarantee that more data will be contiguous on the disk as a solution. Accordingly, what is desired is a method that can be used, independent of the filesystem and without major modification to the filesystem itself, to effectively solve the severe fragmentation problem that exists in DVR disks.